package com.sourcetrip.my;

import com.sourcetrip.my.abs.AbstractBinaryHeap;
import com.sourcetrip.utils.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2020/12/28
 * @description: BinaryHeapV0 的改进版本
 * 改进方面：
 * 1.增加原地建堆（heapify,体现在构造方法中，不是一个个将元素添加，而是直接将数组建堆）
 * 2.结构优化；
 * 3.更加 professional:sift up (上滤)+ sift down（下滤）
 * --
 * 必须牢记的二叉堆的知识点：
 * 1.index 节点的父节点：(index-1)>>1)
 * 2.index 节点的左子节点：(index<<1)+1
 * 3.index 节点的右子节点：(index<<1)+2
 */
public class BinaryHeapV1<E> extends AbstractBinaryHeap<E> implements BinaryTreeInfo {


	//region	constructor

	/**
	 * 比较器
	 *
	 * @param comparator
	 */
	public BinaryHeapV1(Comparator<E> comparator) {
		super(comparator);
	}

	/**
	 *
	 */
	public BinaryHeapV1() {

	}

	/**
	 * 拷贝 array 到
	 *
	 * @param array
	 */
	public BinaryHeapV1(E[] array) {
		size = array.length;
		int capacity = size > DEFAULT_CAPACITY ? size : DEFAULT_CAPACITY;
		elements = (E[]) new Object[capacity];
		System.arraycopy(array, 0, elements, 0, capacity);
		//原地堆化
		heapify();
	}


	//endregion

	/**
	 * 步骤：
	 * 1.判断是否需要扩容；判断是否为空元素；
	 * 2.将元素添加到尾索引；
	 * 3.将尾索引的元素执行上滤！
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		ensureEleNotNull(element);
		//1.确认 本次加进去的数量，是否会触发扩容机制
		ensureCapacity(size + 1);
		elements[size++] = element;
		siftUp(size - 1);
	}

	/**
	 * 步骤：
	 * 1.获取堆顶元素 old value ;
	 * 2.将尾元素放到堆顶的位置；
	 * 3.将堆顶元素下滤（sift down）
	 * 4.返回元素
	 *
	 * @return
	 */
	@Override
	public E remove() {
		E oldValue = get();
		elements[0] = elements[--size];
		siftDown(0);
		return oldValue;
	}

	@Override
	public E replace(E element) {
		E oldValue = get();
		elements[0] = element;
		siftDown(0);
		return oldValue;
	}


	//region	core methods

	/**
	 * 将 elements 中的 index 元素上滤（sift up）
	 *
	 * @param index
	 */
	private void siftUp(int index) {
		int parentIndex = getParentIndex(index);
		while (parentIndex >= 0) {
			int compare = compare(elements[index], elements[parentIndex]);
			if (compare > 0) {
				//当 大于 parent 时执行交换
				swap(index, parentIndex);
				//进入下一轮迭代
				index = parentIndex;
				parentIndex = getParentIndex(index);
			} else {
				break;
			}
		}
	}

	/**
	 * 此时 size 已经是移除后的大小
	 *
	 * @param index
	 */
	private void siftDown(int index) {
		int rightChildIndex = getRightChildIndex(index);
		int biggerIndex = 0;
		while (rightChildIndex < size) {
			//将左节点 与 右节点进行比较
			int compare = compare(elements[rightChildIndex - 1], elements[rightChildIndex]);
			if (compare >= 0) {
				biggerIndex = rightChildIndex - 1;
			} else {
				biggerIndex = rightChildIndex;
			}
			//比较 index 与 biggerIndex
			compare = compare(elements[index], elements[biggerIndex]);
			if (compare > 0) {
				break;
			} else {
				//当元素大于等于时,进行交换（由于是将最后的元素进行下滤，所以即使相等也进行交换，在这一步保持稳定性）
				swap(index, biggerIndex);

				index = biggerIndex;
				rightChildIndex = getRightChildIndex(index);
			}
		}
		//由于判断的是 右子节点，那么多判断一步左子节点是否越界。
		if (rightChildIndex == size) {
			int compare = compare(elements[index], elements[size - 1]);
			if (compare <= 0) {
				swap(index, size - 1);
			}
		}
	}

	/**
	 * 将 elements 原地堆化
	 * 根据我的算法分析：
	 * 只要保证最底层的小二叉堆是稳定的，那么接下来将一个个上层的堆顶元素进行下滤就能最终保证整个堆稳定。
	 * 步骤：
	 * 1.获取最尾部的小二叉堆的堆顶 index，进行下滤；
	 * 2.将 index 递减，直到堆顶；
	 */
	private void heapify() {
		int index = getParentIndex(size - 1);
		for (int i = index; i >= 0; i--) {
			siftDown(i);
		}
	}

	//endregion

	//region	private methods

	/**
	 * 获取 index 的 parent index
	 *
	 * @param index
	 * @return
	 */
	private int getParentIndex(int index) {
		return (index - 1) >> 1;
	}

	/**
	 * 获取 index 节点的左子节点
	 *
	 * @param index
	 * @return
	 */
	private int getLeftChildIndex(int index) {
		return (index << 1) + 1;
	}

	/**
	 * 获取 index 节点的 右子节点
	 *
	 * @param index
	 * @return
	 */
	private int getRightChildIndex(int index) {
		return (index << 1) + 2;
	}

	//endregion
}
